给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
说明：
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
获取链表长度
思路及算法
此前做过一道直接翻转链表的题
对于此题的K 个一组，意思则是分小组进行翻转。
例如： [1, 2, 3, 4, 5, 6, 7, 8] k = 3
1, 2, 3 和 4, 5, 6各为一组并翻转, 7, 8为一组，因数量未满3，所以不翻转
最简单的分组方式，就是链表总长度整除k，故需要事先知道链表的长度length
cur = head
length = 0
while cur:
cur = cur.next
length += 1
## 需要翻转组的数量
length // k
看到这里，emmm，感觉蛮简单。确实思路就是这样的，麻烦在编码上。
1 -> 2 - > 3 -> 4 将123翻转后（<- 1 <- 2 <- 3 4 ->），如何才能1的指针域指向4
将整个链表看做三部分（已翻转， 待翻转， 未翻转）
在当前分组做翻转时，应该保存下一组的起始节点，使得当前组翻转完成后可以去连接下一分组
定义一个头结点dummy且dumm.next = head
定义prev变量，保存上一个分组的尾节点，初始prev = dummy
定义start变量，保存当前分组的首节点，start = prev.next
先来简单看下如何完成一次分组链表翻转
# 设置当前分组的首节点
start = prev.next
# prev.next 指向 通过reverse_listnode翻转之后的链表
prev.next = reverse_listnode(start)
好的，现在的情况就是这样的 prev->3->2->1-> None
我们需要将1连接上下一个分组，但是之前也没有保存下一组首节点，这怎么办？
reverse_listnode
# 在翻转链表函数中，必定会走到当前分组的最后一个节点
# 所以可以通过翻转函数来拿到下一组的首节点
def reverse_listnode(head):
nonlocal k # 一组内的k个节点
pre = None
cur = head
for i in range(k):
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre, cur
现在就可以连接下一组
# 设置当前分组的首节点
start = prev.next
# prev.next 指向 通过reverse_listnode翻转之后的链表
prev.next, next_node = reverse_listnode(start)
# 连接下一组, start之前为首节点，翻转之后成为尾节点
start.next = next_node
# 重新设置prev， 为下一组翻转做准备
prev = start
至此，最后再加上循环就搞定了
for _ in range(length // k):
# 设置当前分组的首节点
start = prev.next
# prev.next 指向 通过reverse_listnode翻转之后的链表
prev.next, next_node = reverse_listnode(start)
# 连接下一组, start之前为首节点，翻转之后成为尾节点
start.next = next_node
# 重新设置prev， 为下一组翻转做准备
prev = start
完整代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
def reverse_node(head):
"""
翻转链表
"""
nonlocal k
pre = None
cur = head
for i in range(k):
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre, cur
def listnode_length():
"""
获取链表长度
"""
length = 0
cur = head
while cur:
cur = cur.next
length += 1
return length
dummy = ListNode(None)
dummy.next = head
prev = dummy
length = listnode_length()
for _ in range(length // k):
# 当前分组的起始节点
start = prev.next
# 翻转链表
prev.next, next_node = reverse_node(start)
# 重新连接两个分组
start.next = next_node
# 将prev和end移动至翻转后分组的尾节点
prev = start
return dummy.next
不获取链表长度
参考题解：
具体的可以看大佬的图解：
完整代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
def reverse_node(head):
pre = None
cur = head
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre
dummy = ListNode(None)
dummy.next = head
prev = dummy
end = dummy
while end.next:
for i in range(k):
if not end:
break
end = end.next
if not end:
break
# 当前分组的起始节点
start = prev.next
# 下一个分组的起始节点
temp_next = end.next
# 当前分组的尾节点指向空
end.next = None
# 翻转链表
prev.next = reverse_node(start)
# 重新连接两个分组
start.next = temp_next
# 将prev和end移动至翻转后分组的尾节点
prev = start
end = prev
return dummy.n